/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow(nums, k) {
  const queue = new Array(nums.length).fill(0);
  let bottom = 0;
  let top = -1;
  for (let i = 0; i < k; i += 1) {
    while (top >= bottom && nums[i] > nums[queue[top]]) {
      top -= 1;
    }
    top += 1;
    queue[top] = i;
  }
  const ans = new Array(nums.length - k + 1).fill(nums[queue[bottom]]);
  for (let i = k; i < nums.length; i += 1) {
    while (bottom <= top && queue[bottom] <= i - k) {
      bottom += 1;
    }
    while (top >= bottom && nums[i] > nums[queue[top]]) {
      top -= 1;
    }
    top += 1;
    queue[top] = i;
    ans[i - k + 1] = nums[queue[bottom]];
  }
  return ans;
}

console.log(displayBaseArray(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) === '[3,3,5,5,6,7]');
console.log(displayBaseArray(maxSlidingWindow([1], 1)) === '[1]');
